package com.xy6.algo.force;

/**
 * 蛮力法实现字符串匹配
 * <pre>
 * 长串s1，短串s2，找出s2在s1中首次出现的位置。相当于String.indexOf(String str)。
 * 假设s1长度为m，s2长度为n。
 * 遍历s1每个字符，将当前字符及其后字符与s2每个字符进行匹配，如果都相同，则找到了s2在s1中首次出现的位置，匹配终止。
 * 如果某个字符不同，终止匹配，继续遍历s1下一个字符。
 * 
 * 时间复杂度：O(mn)
 * 
 * jdk中的字符串匹配算法为改进的朴素算法（Naive String Matching Algorithm）
 * 时间复杂度为：O((n-m+1)*m)
 * </pre>
 * 
 * @author zhang
 * @since 2017-12-19
 */
public class StringMatch {

	public static void main(String[] args){
		System.out.println(calc("abc","a"));
		System.out.println(calc("abcabc","aa"));
		System.out.println(calc("abc","c"));
		String s1 = "abcde";
		String s2 = "cd";
		System.out.println(s1.indexOf(s2));
	}
	
	/**
	 * 找出字符串s2在s1中首次出现的位置
	 * 
	 * @param s1 
	 * @param s2
	 */
	public static int calc(String s1, String s2){
		for(int i=0; i<s1.length(); i++){
			boolean match = true;
			int start = i;
			for(int j=0; j<s2.length(); j++){
				if(s1.charAt(start++) == s2.charAt(j)){
					continue;
				} else {
					match = false;
					break;
				}
			}
			if(match){
				return i;
			}
		}
		return -1;
	}
	
}
